#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<time.h>
#include<stdlib.h>

#define TRUE 1
#define FALSE 0
#define ERROR -1
#define SC(x) scanf("%d",&x)
#define ABS(x) (((x)<0)?-(x):(x))

typedef long long LONG;
typedef char BOOL;

void print(int*a,int n){
    int i;
    for(i=0;i<n;i++)
        printf("%d ",a[i]);
    printf("\n");
}
BOOL prime(int n){
    if(n<0)n=ABS(n);
    if(n==2)
        return TRUE;
    if(n<2||n%2==0)
        return FALSE;
    int c;
    for(c=3; c*c<=n; c+=2)
        if(n%c==0)
            return FALSE;
    return TRUE;
}
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
